/**
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 **/

// TIPS:双指针
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int flag = nums.size()-1;
        for(int i=0; i<=flag; i++){
            // pow(x , y) ,x的y次幂
            nums[i] = nums[i]*nums[i];
        }

        vector<int> ans(flag+1);
        // 用一个新的vector存放比较大小后的结果，按从大到小逆序放入
        for(int i=0, j=flag, pos=flag; i<=j;){
            // 这里也可以先不把平方算出来，而是在比较时再计算平方
            if(nums[i]<nums[j]){
                ans[pos] = nums[j];
                --j;
            }
            else{
                ans[pos] = nums[i];
                ++i;
            }
            --pos;
        }
        return ans;
    }
};

// Solution 2:直接暴力排序
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        // 利用 区间遍历 简化代码
        vector<int> ans;

        for(int num:nums){
            // 区间遍历：给循环提供一个容器，它帮你迭代。类似python
            // Strings,arrays,和所有的STL容器可以被新的区间迭代方式迭代
            ans.push_back(num*num);

        }
        sort(ans.begin(), ans.end());
        return ans;

    }
};


// Solution 3:双指针归并排序
// 如果数组nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。
// 如果我们能够找到数组 nums 中负数与非负数的分界线，那么就可以用类似「归并排序」的方法
// 设neg为数组nums中负数与非负数的分界线，那么nums[0]到nums[neg] 单调递减，nums[neg+1]到nums[n−1]单调递增。
// 得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。使用两个指针分别指向位置neg和neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        int negative = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                negative = i;
            } else {
                break;
            }
        }

        vector<int> ans;
        int i = negative, j = negative + 1;
        while (i >= 0 || j < n) {
            if (i < 0) {
                ans.push_back(nums[j] * nums[j]);
                ++j;
            }
            else if (j == n) {
                ans.push_back(nums[i] * nums[i]);
                --i;
            }
            else if (nums[i] * nums[i] < nums[j] * nums[j]) {
                ans.push_back(nums[i] * nums[i]);
                --i;
            }
            else {
                ans.push_back(nums[j] * nums[j]);
                ++j;
            }
        }

        return ans;
    }
};

